package dp;

import java.util.Arrays;
import java.util.Scanner;

//最长递增子序列
public class LongestIncreaseSequece {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int testNumber = scanner.nextInt();
		int[] array;
		int count = 1;
		int arrayLength;
		while (count++ <= testNumber) {
			arrayLength = scanner.nextInt();
			array = new int[arrayLength];
			for (int i = 0; i < arrayLength; i++) {
				array[i] = scanner.nextInt();
			}
			getLongstSeq(array);
			getLongestSeq(array);
		}
		scanner.close();
	}

	// 最普通的dp
	// 设f(i)表示L中以a[i]为末元素的最长递增子序列的长度。则有如下的递推方程：
	// f(i) = max(f(i - 1),f(i - 2),...,f(1),f(0)) + 1；(j < i且aj < ai)用一个dp[i]保存当前的f(i)值
	
	// 这个递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在i前面且小于ai的元素aj，即j < i且aj < ai。
	// 如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，
	// 那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于f(j)最大的那个aj为末元素的递增子序列最末
	// 再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
	public static int getLongstSeq(int[] array) {
		if (array == null || array.length == 0) {
			return 0;
		}
		int[] longest = new int[array.length];
		int max = 0;
		Arrays.fill(longest, 1); // 初始全部为1
		int j;
		// int temp;
		for (int i = 0; i < longest.length; i++) {
			// 找最大的f[j],使得longest[i]最大
			for (j = i - 1; j >= 0; j--) {
				// if (array[j] < array[i]) {
				// temp = longest[j] + 1;
				// if (temp > longest[i])
				// longest[i] = temp;
				// }
				// array[i] < array[j] 时，并且当前longest[i]小于 longest[j] + 1
				if (array[j] < array[i] && longest[j] + 1 > longest[i]) {
					longest[i] = longest[j] + 1;
				}
			}
			if (longest[i] > max) {
				max = longest[i];
			}
		}
		System.out.println("the LIS is " + max);
		for (int i : longest) {
			System.out.print(i + " ");
		}
		System.out.println();
		return max;
	}

	// http://www.cnblogs.com/lonelycatcher/archive/2011/07/28/2119123.html
	// 由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与暴力求解相比没有任何进步。
	// 在计算每一个f(i)时，都要找出最大的f(j)(j<i)来，由于f(j)没有顺序，只能顺序查找满足aj<ai最大的f(j)，
	// 如果能将让f(j)有序
	// 就可以使用二分查找，这样算法的时间复杂度就可能降到O(nlogn)。
	// 用一个数组ends来存储“子序列的”最大递增子序列的最末元素，即有 ends[f(j)] = aj
	// 在计算f(i)时，在数组ends中用二分查找法找到满足j < i且ends[f(j)] = aj < ai的最大的j,并将ends[f[j] + 1]置为ai。
	public static int getLongestSeq(int[] array) {
		int[] longest = new int[array.length];
		int[] ends = new int[array.length];
		ends[0] = array[0]; // 初始值为array[0]
		longest[0] = 1;
		int left = 0, middle = 0, right = 0; // l,r,m分别为二分查找的上界，下界和中点；
		int r = 0; // 用来标记右边界
		int max = 0;
		for (int i = 1; i < array.length; i++) {
			left = 0;
			right = r;
			// 二分查找最左边大于ai的元素
			while (left <= right) {
				middle = (left + right) / 2;
				if (array[i] > ends[middle]) {
					left = middle + 1;
				} else {
					right = middle - 1;
				}
			}
			r = Math.max(r, left); // 更新r的值
			// 如果没有找到，那么left会等于right + 1，将array[i]加入ends数组，然后r也相应的更新
			ends[left] = array[i];
			longest[i] = left + 1; // left为下标，所以需要加1
			if (longest[i] > max) {
				max = longest[i];
			}
		}
		for (int i : longest) {
			System.out.print(i + " ");
		}
		return max;
	}
	
	//Binary Search + Dp
	//The idea is that as you iterate the sequence, 
//	you keep track of the minimum value a subsequence of given length might end with
//	dp[i] is the minimum value a subsequence of length i + 1 might end with. 
	public static int lengthOfLIS(int[] nums){
		if(nums == null || nums.length <= 0){
			return 0;
		}
		
		int[] dp = new int[nums.length];
		int maxLength = 0;
		int index = 0;
		for(int i = 0; i < nums.length; i++){
			index = Arrays.binarySearch(dp, 0, maxLength, nums[i]);
			if(index < 0){
				//can't find 
				index = 0;
			}
			dp[index] = nums[i];
			if(index == maxLength){
				maxLength++;
			}
		}
		return maxLength;
	}
}
